use std::cell::RefCell;
use std::cmp::Ordering;
use std::default::Default;
use std::fmt;
use std::rc::Rc;

use crate::nineteen::*;
pub struct DisjointSetNode {
    v: u32,
    p: RefCell<Option<Rc<DisjointSetNode>>>,
    rank: RefCell<u32>,
}

impl fmt::Display for DisjointSetNode {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        if let Some(p) = self.get_p() {
            write!(f, "{}({})-{}", self.get_v(), p.get_v(), self.get_rank())
        } else {
            write!(f, "{}(null)-{}", self.get_v(), self.get_rank())
        }
    }
}

impl DisjointSetNode {
    pub fn build(v: u32) -> Rc<DisjointSetNode> {
        Rc::new(DisjointSetNode {
            v,
            p: RefCell::new(None),
            rank: RefCell::new(0),
        })
    }
    pub fn get_v(&self) -> u32 {
        self.v
    }
    pub fn get_p(&self) -> Option<Rc<DisjointSetNode>> {
        unsafe {
            if let Some(p) = &(*(self.p.as_ptr())) {
                Some(Rc::clone(p))
            } else {
                None
            }
        }
    }
    pub fn get_rank(&self) -> u32 {
        unsafe { *(self.rank.as_ptr()) }
    }
    pub fn set_p(&self, p: Rc<DisjointSetNode>) {
        *(self.p.borrow_mut()) = Some(Rc::clone(&p));
    }
    pub fn set_rank(&self, rank: u32) {
        *(self.rank.borrow_mut()) = rank;
    }
    pub fn rank_inc(&self) {
        self.set_rank(self.get_rank() + 1);
    }
    pub fn is_root(&self) -> bool {
        unsafe { (*(self.p.as_ptr())).is_none() }
    }
}

pub struct DisjointSetForest {
    node_list: Vec<Rc<DisjointSetNode>>,
}

impl fmt::Display for DisjointSetForest {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        for node in self.node_list.iter() {
            println!("{}", node);
        }
        write!(f, "Over!")
    }
}

impl DisjointSetForest {
    pub fn build() -> Self {
        DisjointSetForest { node_list: vec![] }
    }
    pub fn make_set(&mut self, x: u32) {
        self.node_list.push(Rc::clone(&DisjointSetNode::build(x)));
    }
    pub fn union(&mut self, x: u32, y: u32) {
        let x_node = self.node_find(x);
        let y_node = self.node_find(y);
        let left = self.find_set(x_node);
        let right = self.find_set(y_node);
        self.link(left, right);
    }
    fn link(&mut self, x: Rc<DisjointSetNode>, y: Rc<DisjointSetNode>) {
        println!("link: x: {}, y: {}", x.get_v(), y.get_v());
        if x.get_rank() > y.get_rank() {
            y.set_p(Rc::clone(&x));
        } else {
            x.set_p(Rc::clone(&y));
            if x.get_rank() == y.get_rank() {
                y.rank_inc();
            }
        }
    }
    pub fn find_set_root(&self, x: u32) -> u32 {
        let mut node = self.node_find(x);
        while !(node.is_root()) {
            node = node.get_p().unwrap();
        }
        node.get_v()
    }
    fn find_set(&self, x: Rc<DisjointSetNode>) -> Rc<DisjointSetNode> {
        if !(x.is_root()) {
            let node = self.find_set(x.get_p().unwrap());
            x.set_p(Rc::clone(&node));
            Rc::clone(&node)
        } else {
            Rc::clone(&x)
        }
    }
    fn node_find(&self, x: u32) -> Rc<DisjointSetNode> {
        let mut res = DisjointSetNode::build(0);
        for node in self.node_list.iter() {
            if node.get_v() == x {
                res = Rc::clone(node);
                break;
            }
        }
        res
    }
}

pub struct MinimumSpanningTreeKruskal {
    dsf: DisjointSetForest,
}

impl MinimumSpanningTreeKruskal {
    pub fn build() -> Self {
        MinimumSpanningTreeKruskal {
            dsf: DisjointSetForest::build(),
        }
    }

    pub fn mst_kruskal(&mut self, nodes: Vec<u32>, edges: Vec<(u32, u32, u32)>) -> Vec<(u32, u32)> {
        let mut a: Vec<(u32, u32)> = vec![];
        for node in nodes.iter() {
            self.dsf.make_set(*node);
        }
        println!("After make_set: \n{}", self.dsf);
        let mut sort_edges = edges;
        sort_edges.sort_by(|x, y| x.2.cmp(&y.2));
        println!("Sort Edges: \n{:?}", sort_edges);
        for edge in sort_edges.iter() {
            println!("edge: {}-> {}", edge.0, edge.1);
            if self.dsf.find_set_root(edge.0) != self.dsf.find_set_root(edge.1) {
                println!("Union~");
                a.push((edge.0, edge.1));
                self.dsf.union(edge.0, edge.1);
                println!("{}", self.dsf);
            }
        }
        a
    }
}
/*
   let mut m = MinimumSpanningTreeKruskal::build();
   let nodes: Vec<u32> = vec![1, 2, 3, 4, 5, 6, 7, 8, 9];
   let mut edges: Vec<(u32, u32, u32)> = vec![];
   edges.push((1, 2, 4));
   edges.push((1, 8, 8));
   edges.push((2, 3, 8));
   edges.push((2, 8, 11));
   edges.push((3, 4, 7));
   edges.push((3, 6, 4));
   edges.push((3, 9, 2));
   edges.push((4, 5, 9));
   edges.push((4, 6, 14));
   edges.push((5, 6, 10));
   edges.push((6, 7, 2));
   edges.push((7, 8, 1));
   edges.push((7, 9, 6));
   edges.push((8, 9, 7));
   let a = m.mst_kruskal(nodes, edges);
   println!("{:?}", a);
*/

#[derive(Clone)]
pub struct MergeableHeapNodeT {
    k: u32,
    w: RefCell<u32>,
    p: RefCell<Option<u32>>,
    is_tree_node: RefCell<bool>,
}

impl MergeableHeapNodeT {
    pub fn build(k: u32) -> Rc<MergeableHeapNodeT> {
        Rc::new(MergeableHeapNodeT {
            k,
            w: RefCell::new(u32::MAX),
            p: RefCell::new(None),
            is_tree_node: RefCell::new(false),
        })
    }
    pub fn get_key(&self) -> u32 {
        self.k
    }
    pub fn get_w(&self) -> u32 {
        unsafe { *(self.w.as_ptr()) }
    }
    pub fn get_p(&self) -> Option<u32> {
        unsafe { *(self.p.as_ptr()) }
    }
    pub fn is_tree_node(&self) -> bool {
        unsafe { *(self.is_tree_node.as_ptr()) }
    }

    pub fn set_w(&self, w: u32) {
        *(self.w.borrow_mut()) = w;
    }
    pub fn set_p(&self, p: u32) {
        *(self.p.borrow_mut()) = Some(p);
    }
    pub fn to_tree(&self) {
        *(self.is_tree_node.borrow_mut()) = true;
    }
}

impl PartialEq for MergeableHeapNodeT {
    fn eq(&self, other: &Self) -> bool {
        self.get_w() == other.get_w()
    }
}

impl PartialOrd for MergeableHeapNodeT {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.get_w().cmp(&other.get_w()))
    }
}
impl Default for MergeableHeapNodeT {
    fn default() -> Self {
        MergeableHeapNodeT {
            k: 0_u32,
            w: RefCell::new(u32::MIN),
            p: RefCell::new(None),
            is_tree_node: RefCell::new(false),
        }
    }
}

impl fmt::Display for MergeableHeapNodeT {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(
            f,
            "{}-{}-{:?}-{}",
            self.get_key(),
            self.get_w(),
            self.get_p(),
            self.is_tree_node()
        )
    }
}

pub struct NewAdjacencyListNode {
    v: Rc<MergeableHeapNodeT>,
    list: Vec<(Rc<MergeableHeapNodeT>, u32)>,
}

impl NewAdjacencyListNode {
    pub fn build(v: Rc<MergeableHeapNodeT>, list: Vec<(Rc<MergeableHeapNodeT>, u32)>) -> Self {
        let mut v_list = vec![];
        for (v, w) in list.iter() {
            v_list.push((Rc::clone(v), *w));
        }
        NewAdjacencyListNode {
            v: Rc::clone(&v),
            list: v_list,
        }
    }
    pub fn get_v(&self) -> Rc<MergeableHeapNodeT> {
        Rc::clone(&self.v)
    }
    pub fn get_list(&self) -> Vec<(Rc<MergeableHeapNodeT>, u32)> {
        let mut res = vec![];
        for (node, w) in self.list.iter() {
            res.push((Rc::clone(node), *w));
        }
        res
    }
}

pub struct NewAdjacencyList {
    list: Vec<NewAdjacencyListNode>,
}

impl NewAdjacencyList {
    pub fn build(list: Vec<NewAdjacencyListNode>) -> Self {
        NewAdjacencyList { list }
    }
    pub fn get_node_list(&self, v: Rc<MergeableHeapNodeT>) -> Vec<(Rc<MergeableHeapNodeT>, u32)> {
        let mut res = vec![];
        for node in self.list.iter() {
            if node.get_v().get_key() == v.get_key() {
                res = node.get_list();
                break;
            }
        }
        res
    }
}
pub struct MinimumSpanningTreePrim;

impl MinimumSpanningTreePrim {
    pub fn mst_prim(g: NewAdjacencyList, r: Rc<MergeableHeapNodeT>) -> Vec<u32> {
        let mh = MergeableHeap::build();
        r.set_w(0);
        let mut node_vec = vec![];
        let mut temp = MergeableHeapNode::build(Rc::clone(&r));
        node_vec.push(Rc::clone(&temp));
        println!("{}", temp);
        mh.fib_heap_insert(Some(MergeableHeapNode::build(Rc::clone(&r))));
        let mut g_list_iter = g.list.iter();
        g_list_iter.next();
        for node in g_list_iter {
            println!("{}", node.get_v());
            temp = MergeableHeapNode::build(Rc::clone(&(node.get_v())));
            node_vec.push(Rc::clone(&temp));
            println!("{}", temp);
            mh.fib_heap_insert(Some(temp));
        }
        println!("{}", mh);
        let mut u;
        // for (node, w) in g.get_node_list(Rc::clone(&u)).iter() {
        //     if !(node.is_tree_node()) && *w < node.get_w() {
        //         node.set_p(u.get_key());
        //         for heap_node in node_vec.iter() {
        //             if heap_node.get_key().get_key() == node.get_key() {
        //                 node.set_w(*w);
        //                 mh.fib_heap_decrease_key(Some(Rc::clone(heap_node)), Rc::clone(node));
        //                 break;
        //             }
        //         }
        //     }
        // }
        // println!("{}", mh);
        let mut res = vec![];
        while !(mh.is_empty()) {
            u = mh.fib_heap_extract_min().unwrap().get_key();
            res.push(u.get_key());
            u.to_tree();
            for (node, w) in g.get_node_list(Rc::clone(&u)).iter() {
                if !(node.is_tree_node()) && *w < node.get_w() {
                    node.set_p(u.get_key());
                    println!("{}", node);
                    for heap_node in node_vec.iter() {
                        if heap_node.get_key().get_key() == node.get_key() {
                            node.set_w(*w);
                            mh.fib_heap_decrease_key(Some(Rc::clone(heap_node)), Rc::clone(node));
                            break;
                        }
                    }
                }
            }
            mh.fib_remin();
            println!("{}", mh);
        }
        res
    }
}
/*
let mut m = vec![];
    for i in 1_u32..=9_u32 {
        m.push(MergeableHeapNodeT::build(i));
    }
    let mut ajc = vec![];
    ajc.push(NewAdjacencyListNode::build(
        Rc::clone(&m[0]),
        vec![(Rc::clone(&m[1]), 4), (Rc::clone(&m[7]), 8)],
    ));
    ajc.push(NewAdjacencyListNode::build(
        Rc::clone(&m[1]),
        vec![
            (Rc::clone(&m[0]), 4),
            (Rc::clone(&m[2]), 8),
            (Rc::clone(&m[7]), 11),
        ],
    ));
    ajc.push(NewAdjacencyListNode::build(
        Rc::clone(&m[2]),
        vec![
            (Rc::clone(&m[1]), 8),
            (Rc::clone(&m[3]), 7),
            (Rc::clone(&m[5]), 4),
            (Rc::clone(&m[8]), 2),
        ],
    ));

    ajc.push(NewAdjacencyListNode::build(
        Rc::clone(&m[3]),
        vec![
            (Rc::clone(&m[2]), 7),
            (Rc::clone(&m[4]), 9),
            (Rc::clone(&m[5]), 14),
        ],
    ));
    ajc.push(NewAdjacencyListNode::build(
        Rc::clone(&m[4]),
        vec![(Rc::clone(&m[3]), 9), (Rc::clone(&m[5]), 10)],
    ));
    ajc.push(NewAdjacencyListNode::build(
        Rc::clone(&m[5]),
        vec![
            (Rc::clone(&m[2]), 4),
            (Rc::clone(&m[3]), 14),
            (Rc::clone(&m[4]), 10),
            (Rc::clone(&m[6]), 2),
        ],
    ));

    ajc.push(NewAdjacencyListNode::build(
        Rc::clone(&m[6]),
        vec![
            (Rc::clone(&m[5]), 2),
            (Rc::clone(&m[7]), 1),
            (Rc::clone(&m[8]), 6),
        ],
    ));
    ajc.push(NewAdjacencyListNode::build(
        Rc::clone(&m[7]),
        vec![
            (Rc::clone(&m[0]), 8),
            (Rc::clone(&m[1]), 11),
            (Rc::clone(&m[6]), 1),
            (Rc::clone(&m[8]), 7),
        ],
    ));
    ajc.push(NewAdjacencyListNode::build(
        Rc::clone(&m[8]),
        vec![
            (Rc::clone(&m[2]), 2),
            (Rc::clone(&m[6]), 6),
            (Rc::clone(&m[7]), 7),
        ],
    ));

    let res = MinimumSpanningTreePrim::mst_prim(NewAdjacencyList::build(ajc), Rc::clone(&m[0]));
    println!("{:?}", res);
 */
